package my.union;

import java.util.Arrays;

/**
 * Quick Union - 基于rank的优化
 *
 * @author AJun
 * @date 2020/11/1
 */
public class UnionFind_QU_R extends UnionFind_QU {

    private final int[] ranks;

    public UnionFind_QU_R(int capacity) {
        super(capacity);

        ranks = new int[capacity];
        // 初始化都是 1
        Arrays.fill(ranks, 1);
    }

    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) {
            return;
        }

        if (ranks[p1] < ranks[p2]) {
            parents[p1] = p2;
        } else if (ranks[p1] > ranks[p2]) {
            parents[p2] = p1;
        } else {
            parents[p1] = p2;
            // 如果高度相等则将 p1 嫁接到 p2 上，并将 p1 的高度 +1
            ranks[p2] += 1;
        }
    }

}
